package leecode

func arrayRankTransform(arr []int) []int {
	if len(arr) < 1 {
		return []int{}
	}
	temp := make([]int, len(arr))
	copy(temp, arr)
	left := 0
	right := len(arr) - 1
	process1331(arr, left, right)
	//循环遍历数组
	arrMap := make(map[int]int, len(arr)) //key为数组中的元素 , value为对应下标
	count := 0
	for i := 0; i < len(arr); i++ {
		_, ok := arrMap[arr[i]]
		if !ok {
			//保证下标尽可能的小
			arrMap[arr[i]] = count
			count++
		}
	}
	result := make([]int, 0, len(arr))
	for i := 0; i < len(temp); i++ {
		result = append(result, arrMap[temp[i]]+1)
	}
	return result
}

// 对数组两侧进行排序
func process1331(arr []int, left, right int) {
	if left == right {
		return
	}
	mid := (left + right) >> 1
	process1331(arr, left, mid)    //对数组左侧进行排序
	process1331(arr, mid+1, right) //对数组右侧进行排序
	merge1331(arr, left, mid, right)
}

// 对数组整体进行排序
func merge1331(arr []int, left, mid, right int) {
	help := make([]int, right-left+1)
	i := 0
	p1 := left
	p2 := mid + 1
	for p1 <= mid && p2 <= right {
		if arr[p1] < arr[p2] {
			help[i] = arr[p1]
			i++
			p1++
		} else {
			help[i] = arr[p2]
			i++
			p2++
		}
	}
	//检测数组左侧是否有未排序的元素
	for p1 <= mid {
		help[i] = arr[p1]
		p1++
		i++
	}
	//检测数组右侧是否有未排序的元素
	for p2 <= right {
		help[i] = arr[p2]
		p2++
		i++
	}
	//改变nums数组中的值
	for i := 0; i < len(help); i++ {
		arr[i+left] = help[i]
	}
}
